/**
  \file dawg.c
  \author Francis Girard
  \date 6 march 2012
  
  Dawg read access utilities.
*/

/*
 *  Copyright (C) 2012, Francis Girard
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "dawg.h"
#include "dawg_bits.h"
#include "wordbuf.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#pragma warning(disable : 4996)


static char _PKC_EOL = '\n';

/**
  Create a dawg structure from binary dawg file.
  
  \param pkcFName The binary dawg file name.
  \return A handle to the created dawg.
*/
H_DAWG dawg_create(const char* pkcFName)
{
  FILE* oBinFile = fopen(pkcFName, "rb");
  int nNbNodes = 0;
  int* pNodes = 0;
  
  if (oBinFile == 0)
    return (H_DAWG) 0;
  fread(&nNbNodes, 4, 1, oBinFile);
  
  pNodes = (int*) malloc(sizeof(int)*(nNbNodes+1));
  fread(pNodes, 4, nNbNodes, oBinFile);
  *(pNodes + nNbNodes) = 0; /* End Mark */
  
  fclose(oBinFile);
  
  return (H_DAWG) pNodes;
}


/**
  Destroy a dawg.
  
  \param hDawg Handle to the dawg (obtained with dawg_create)
*/
void dawg_destroy(H_DAWG hdawg)
{
  int* pNodes = (int*) hdawg;
  free(pNodes);
}


/**
  Finds the longest word into the dawg matching the specified text.
  
  \param hDawg Handle to the dawg (obtained with dawg_create)
  \param pText The input text at the begin of which to find the longest match
  \return A pointer into pText, pointing to one passed the last character of
          the longest matched text. Therefore, if no matching word has been
          found then the parameter pText will be returned.
*/
char* dawg_find_longest(H_DAWG hDawg, char* pText)
{
  int* pNodes = (int*) hDawg;
  char* pTextCur = pText;
  char* pTextEnd = pText;
  unsigned char bEndOfWord;
  unsigned char bEndOfList;
  char letter;
  
  int nPos = 1;
  int node = pNodes[1];
  for ( ; ; )
  {
    letter = node & E_DAWG_LETTER_MASK;
    
    /*
       If the letter at current node match the top letter from input
    */
    if (letter == *pTextCur)
    {
      bEndOfWord = (node & E_DAWG_END_OF_WORD_FLAG) != 0;
      pTextCur++;
      if (bEndOfWord)
      {
        pTextEnd = pTextCur;
      }
      
      /*
         Break and return if no more letter from input
      */
      if (*pTextCur == 0)
        return pTextEnd;
      
      /*
         Otherwise, go to the first possible child
         childIndex
      */
      nPos = (node & E_DAWG_CHILD_INDEX_MASK) >> E_DAWG_CHILD_BIT_SHIFT;
      if (nPos == 0)
        return pTextEnd; /* No more childs */
    }
    
    /*
       If the letter at current node did NOT match the top letter from input
    */
    else
    {
      bEndOfList = (node & E_DAWG_END_OF_LIST_FLAG) != 0;
      
      /*
         If this is not the end of possible childs, go to the next child.
      */
      if (!bEndOfList && letter < *pTextCur)
      {
        nPos++;
      }
      
      /*
         If this is the end of possible childs then there is nothing better
         to hope for
      */
      else
      {
        return pTextEnd;
      }
    }
    
    node = pNodes[nPos];
  }
  
  /*
     We should never get here but just stop the compiler from complaining ...
  */
  return pTextEnd;
}


/**
  Dumps all the words of the specified dawg into the specified file.
  
  \param hDawg Handle to the dawg (obtained with dawg_create)
  \param pOutFile The file where to dump the strings
*/
void _dawg_dump(H_DAWG hDawg, unsigned int nPos, FILE* pOutFile, H_WordBuf hWordBuf)
{
  int* pNodes = (int*) hDawg;
  unsigned char bEndOfWord;
  unsigned char bEndOfList;
  char letter;
  unsigned int nChildIdx;
  
  for ( ; ; )
  {
    int node = pNodes[nPos];
    
    /*
      Fetch letter
    */
    letter = node & E_DAWG_LETTER_MASK;
    WordBuf_Append(hWordBuf, letter);
    
    /*
      Dump word if we have one
    */
    bEndOfWord = (node & E_DAWG_END_OF_WORD_FLAG) != 0;
    if (bEndOfWord)
    {
      fwrite(WordBuf_GetWord(hWordBuf),
             sizeof(char),
             WordBuf_GetSize(hWordBuf),
             pOutFile);
      fwrite(&_PKC_EOL,
             sizeof(char),
             1,
             pOutFile);
    }
    
    /*
      Deep-first recursive descent
    */
    nChildIdx = (node & E_DAWG_CHILD_INDEX_MASK) >> E_DAWG_CHILD_BIT_SHIFT;
    if (nChildIdx > 0)
    {
      _dawg_dump(hDawg, nChildIdx, pOutFile, hWordBuf);
    }
    
    /*
      Loop on breadth
    */
    WordBuf_Pop(hWordBuf);
    bEndOfList = (node & E_DAWG_END_OF_LIST_FLAG) != 0;
    if (bEndOfList)
    {
      return;
    }
    nPos++;
  }
}


/**
  Dumps all the directed acyclic word graph structure.
  
  \param hDawg Handle to the dawg (obtained with dawg_create)
  \param pOutFile The file where to dump the strings
*/
void dawg_dump_tree(H_DAWG hDawg, FILE* pOutFile)
{
  char sChildIdx[32];
  char sPos[32];
  
  int* pNodes = (int*) hDawg;
  unsigned char bEndOfWord;
  unsigned char bEndOfList;
  char letter;
  unsigned int nChildIdx;
  
  unsigned int nPos = 1;
  
  for ( ; ; )
  {
    int node = pNodes[nPos];
    if (node == 0)
    {
      break;
    }
    
    /* Node number */
    snprintf(sPos, 32, "%d", nPos);

    fwrite(sPos, sizeof(char)*strlen(sPos), 1, pOutFile);
    fwrite("\t", sizeof(char), 1, pOutFile);
    
    /* Letter. */
    letter = node & E_DAWG_LETTER_MASK;
    fwrite(&letter, sizeof(char), 1, pOutFile);
    
    /* End of word? */
    bEndOfWord = (node & E_DAWG_END_OF_WORD_FLAG) != 0;
    if (bEndOfWord)
      fwrite("\tEOW\t", sizeof(char), 5, pOutFile);
    else
      fwrite("\t---\t", sizeof(char), 5, pOutFile);
    
    /* Child index. */
    nChildIdx = (node & E_DAWG_CHILD_INDEX_MASK) >> E_DAWG_CHILD_BIT_SHIFT;
    snprintf(sChildIdx, 32, "%d", nChildIdx);
    fwrite(sChildIdx, sizeof(char)*strlen(sChildIdx), 1, pOutFile);
    
    /* End of list. */
    bEndOfList = (node & E_DAWG_END_OF_LIST_FLAG) != 0;
    if (bEndOfList)
      fwrite("\tEOL\n", sizeof(char), 5, pOutFile);
    else
      fwrite("\t---\n", sizeof(char), 5, pOutFile);
    
    nPos++;
  }
}


/**
  Dumps all the words into the specified dawg into the specified file.
  
  \param hDawg Handle to the dawg (obtained with dawg_create)
  \param pOutFile The file where to dump the strings
*/
void dawg_dump(H_DAWG hDawg, FILE* pOutFile)
{
  H_WordBuf hWordBuf = WordBuf_Create(0);
  unsigned int nPos = 1;
  _dawg_dump(hDawg, nPos, pOutFile, hWordBuf);
}


